\chapter{Version MPI}

\section{Choix d'implémentation}

Pour faciliter la communication entre les noeuds, nous avons décidé de travailler sur des tableaux unidimensionnels.
De ce fait, le maître calcule les portions du tableau \texttt{board} à traiter de manière statique en fonction du nombre de noeuds,
et les envoie une par une à chacun d'eux (chaque noeud ne traite qu'une seule portion), accompagnées des valeurs nécessaires au bon déroulement du traitement de ces
dernières. Une portion du tableau à traiter représente un certain nombre de lignes, à laquelle sont ajoutées une ligne 
supérieure à synchroniser avec le voisin précédent, et une ligne inférieure à synchroniser avec le voisin suivant. Comme 
les noeuds ne partagent rien, une barrière locale a été mise en place grâce aux fonctions \texttt{MPI\_Isend} et \texttt{MPI\_Wait} pour 
leur permettre de synchroniser ces lignes lorsqu'ils ont fini de traiter leurs bordures (de la même manière que 
pour la version \emph{pthread} du raffinement). En pratique, un noeud envoie ces deux lignes à ses voisins suivant et précédent lorsqu'il a fini de traiter ses bordures, traite ensuite sa portion intérieure, puis attend de recevoir ses deux lignes extérieures de ses voisins précédent et suivant. Après que toutes les itérations aient été effectuées, les noeuds renvoient un par un leur portion de tableau et la valeur des cellules vivantes de cette portion au maître, afin qu'il reconstruise le tableau et calcule le nombre
de cellules vivantes global par réduction.

\section{Mesures}

Il n'y a pas de réelle utilité à faire renvoyer la portion de tableau de chaque noeud au maître dans le cas de très grands tableaux,
nous avons donc effectué les mesures en considérant uniquement la synchronisation du nombre de cellules vivantes à la fin de l'exécution du programme.

\section{Résultats}

\begin{center}
\includegraphics[scale=0.65]{./img/exec_mpi.png}

\includegraphics[scale=0.65]{./img/speedup_mpi.png}
\end{center}

\newpage
Sachant que nous travaillons sur les quatre machines \emph{infini} qui possèdent huit coeurs chacune, nous avons pensé avant d'effectuer les mesures que le temps minimal
serait obtenu pour 33 noeuds lancés (4*8 + le maître), hors il s'avère que ce temps minimal est en fait obtenu pour 17 noeuds (16 + le maître). Le courbe de \emph{speedup} permet de mettre
en valeur ce raisonnement, le \emph{speedup} ne cesse d'augmenter jusqu'à 17 noeuds lancés pour atteindre environ 21, soit un temps d'exécution 21 fois plus rapide que la version séquentielle,
puis il décroît rapidement jusqu'à repasser en dessous du \emph{speedup} où nous avons un noeud lancé par machine.

On pourrait expliquer ce phénomène par la nature de l'architecture des machines \emph{infini}. En effet, les machines \emph{infini} sont de type \emph{SMP}, c'est à dire que la mémoire est partagée par tous les \emph{threads}. Nous pensons qu'à partir d'un certains nombre de \emph{threads}, le total de l'espace mémoire que chaque \emph{thread} alloue dépasse la taille du cache. Du coup ils \textit{se marchent dessus} en provoquant des défauts de cache à répétition. Le manque de mémoire dans le cache comparé au nombre important de \emph{threads} implique un rechargement systématique lorsqu'un \emph{thread} reprend la main. Sachant qu'un défaut de cache correspond à environ une vingtaine de cycles d'horloge, et au vue du grand nombre de \emph{threads} lancés (supérieur à 20), il semble que le nombre de \emph{threads} idéal se situe à 17 (16 + 1), peut être le nombre idéal où le cache est parfaitement rempli par tous les threads sans toutefois déborder.

\section{Comparaison}

\begin{center}
\includegraphics[scale=0.65]{./img/exec_mpi_r.png}

\includegraphics[scale=0.65]{./img/speedup_mpi_r.png}
\end{center}

Grâce au réseau \emph{Infiniband} des machines \emph{inifini}, la version \emph{MPI} est de loin plus performante que la version \emph{pthread} du raffinement. Là où sur la version \emph{pthread} nous
avions un résultat optimal pour 8 \emph{threads} (sur une machine à 8 coeurs), nous avons avec la version \emph{MPI} un résultat optimal pour 16 noeuds lancés (sans le maître, sur quatre machines à 8 coeurs), et un temps d'exécution
cinq fois plus rapide que pour le temps optimal de la version \emph{pthread}. Par contre, lorsque nous dépassons un certain nombre de noeuds lancés (ici environ 50), la version \emph{pthread} devient plus performante. Cela peut s'expliquer par le fait que \emph{MPI} soit borné par une autre condition : l'utilisation d'un réseau. Au delà d'un certain nombre de noeuds lancés, les appels aux fonctions \texttt{MPI\_Isend} et \texttt{MPI\_Irecv} peuvent entraîner une congestion du réseau. Le facteur limitant devient alors la performance réseau, et non plus la performance des machines.


\chapter{Difficultés rencontrées}

\section{Version Pthread}
Lorsque nous avons implémenté la version simple, nous avons mis du temps à nous rendre compte que nous avions des soucis au niveau de la gestion des indices du tableau, et non au niveau de la méthode de parallélisation, qui elle était bonne depuis le départ.

De même, après avoir réglé ces problèmes d'indices, nous avions une mauvaise synchronisation des \emph{threads} et ne savions pas réellement où placer notre barrière (limitée au voisinage). Il faillait en l'occurrence deux barrières, une après la recopie des données, et une autre après le calcul du nombre de voisins. 

Une fois ces deux modifications prises en compte, nous avons obtenu le résultat attendu.

\section{Version MPI}
Il est important de préciser que la plus grosse partie du travail de compréhension a été effectuée pour la version simple \emph{pthread}, il n'était donc question ici que d'adapter le code aux fonctions \emph{MPI}, les difficultés rencontrées dans cette partie ne concernent donc pas la compréhension du projet.

En ce qui concerne la gestion des  tableaux, nous n'avons pas réussi à trouver de méthodes fiables pour transmettre des portions de tableaux bi-dimensionnels entre les noeuds, nous avons donc choisi de travailler sur des tableaux unidimensionnels.

Au niveau du type de données à transmettre entre les noeuds, nous n'avons pas tenu compte de votre remarque\footnote{A propos de l'utilisation du type \texttt{MPI\_CHAR} au lieu de \texttt{MPI\_INT}}, pour la simple et bonne raison que même en travaillant sur des tableaux de caractères et en transmettant des données de type \texttt{MPI\_CHAR}, notre programme ne fonctionnait plus, et comme au moment où nous avons effectué les mesures, il n'y avait personne de connecté sur le réseau \emph{InfiniBand} (visible grâce à la commande \emph{who}), nous avons continué à travailler avec le type \texttt{MPI\_INT}, et n'avons pas rencontré de problèmes de bande passante.
